Лабораторная работа №5

Вероятностные алгоритмы проверки чисел на простоту

Тазаева Анастасия Анатольевна

Российский университет дружбы народов

2025-10-04

Информация

Докладчик

  • Тазаева Анастасия Анатольевна
  • студент группы НФИмд-02-25
  • Российский университет дружбы народов им. П. Лумумбы
  • 1032259385@pfur.ru

Введение

Цель работы

Ознакомиться с алгоритмами проверки чисел на простоту. Реализовать их.

Задачи

Реализовать на языке программирования Julia:

  1. Алгоритм, реализующий тест Ферма.
  2. Алгоритм вычисления числа Якоби.
  3. Алгоритм, реализующий тест Соловея-Штрассена.
  4. Алгоритм, реализующий тест Миллера-Рабина.

Программный код

Алгоритм, реализующий тест Ферма

function test_Ferma(n)
    if n < 5
        return "incorrrect n.please try again \n"
    end
    a = rand(2:n-2)
    r = powermod(a, n-1,n)
    if r == 1
        return "4islo " * string(n) * ", veroyatno, prostoe\n"
    else
        return "4islo " * string(n) * " sostavnoe \n"
    end
end

Алгоритм, реализующий тест Ферма

Рисунок 1: Алгоритм, реализующий тест Ферма. Пример отработки

Алгоритм вычисления числа Якоби

function simvol_Yakobi(n,a)
    if n < 3 || a >= n || a < 0
        return "\nincorrrect n,a.please try again\n"
    end
    g = 1
    a1 = 0
    k = 0
    s = 0
    while a1 != 1
        if 1 == 0
            return 0
        elseif a == 1
            return 1
        end
        a1 = a
        k = 0
        while a1 % 2 == 0
            k += 1
            a1 = round(Int64, a1 / 2)
        end
        if k % 2 == 0 || (k % 2 == 1 && \\
        (n % 8 == 1 || n %8 == 7))
            s = 1
        elseif k % 2 == 1 && (n % 8 == 3 || n % 8 == 5)
            s = -1
        end
        if a1 == 1
            return g*s
        end
        if n%4==3 && a%4==3
            s=-s
        end
        a = n % a1
        n = a1
        g *= s
    end
end

Алгоритм вычисления числа Якоби

Рисунок 2: Алгоритм вычисления числа Якоби. Пример отработки

Алгоритм, реализующий тест Соловея-Штрассена

function test_Soloveya_Shtrassena(n)
    if n < 5
        return "incorrrect n.please try again"
    end
    a = rand(2:n-2)
    r = powermod(a, round(Int64, (n-1)/2), n)
    if r != 1 && r != n-1
        return "4islo " * string(n) * " sostavnoe \n"
    else
        s = simvol_Yakobi(n,a)
        if r == s && r != NaN
            return "4islo " * string(n) * " sostavnoe \n"
        end
        return "4islo " * string(n) * ", veroyatno, prostoe\n"
    end
end

Алгоритм, реализующий тест Соловея-Штрассена

Рисунок 3: Алгоритм, реализующий тест Соловея-Штрассена. Пример отработки

Алгоритм, реализующий тест Миллера-Рабина

function test_Millera_Robina(n)
    if n < 5
        return "Incorrect input."
    end
    r = n-1
    s = 0
    while r % 2 == 0
        s += 1
        r = round(Int64, r / 2)
    end
    a = rand(2:n-2)
    y = powermod(a, r, n)
    if y != 1 && y != n-1
        j = 1
        while j < s-1 && y != n-1
            y = y^2 % n
            if y == 1
                "4islo " * string(n) * " sostavnoe \n"
            end
            j += 1
        end
        if y != n-1
            "4islo " * string(n) * " sostavnoe \n"
        else
            "4islo " * string(n) * ", veroyatno, prostoe\n"
        end
    else
        return "4islo " * string(n) * ", veroyatno, prostoe\n"
    end
end 

Алгоритм, реализующий тест Миллера-Рабина

Рисунок 4: Алгоритм, реализующий тест Миллера-Рабина. Пример отработки

Заключение

Вывод

В ходе лабораторной работы реализованы на языке программирования Julia:

  1. Алгоритм, реализующий тест Ферма.
  2. Алгоритм вычисления числа Якоби.
  3. лгоритм, реализующий тест Соловея-Штрассена.
  4. Алгоритм, реализующий тест Миллера-Рабина.